#include <iostream>
#include <cstdlib>
#include "BinaryTreeNode.h"

template <class T>
class BinaryTree
{
public:
    typedef BinaryTreeNode<T> Node;

protected:
    Node* root;    //The dress of the root node.

public:
    BinaryTree(){root = NULL;};
    BinaryTree(T _data);
    ~BinaryTree();
    void release(Node* _x);
    void inorder_walk(Node* _x) const;
    void inorder_walk() const;
    Node* min(Node* _x) const;
    Node* max(Node* _x) const;
    Node* predecessor(Node* _x) const;
    Node* successor(Node* _x) const;
    Node* tree_search(T k) const;
    void insert(T _data);
    void insert(Node* _new);
    void transplant(Node* _u, Node* _v);
    void del(Node* _x);
};

template <class T>
BinaryTree<T>::BinaryTree(T _data)
{
    Node* p = new Node(_data);
    if (root == NULL)
	root = p;
}

template <class T>
BinaryTree<T>::~BinaryTree()
{
    release(root);
};

template<class T>
void BinaryTree<T>::release(Node* _x)
{
    if (_x != NULL)
    {
	release(_x->left);
	release(_x->right);
	delete _x;
    }	
}

template <class T>
void BinaryTree<T>::inorder_walk(Node* _x) const
{
    if (_x != NULL)
    {
	inorder_walk(_x->left);
	std::cout << _x->data << "\t";
	inorder_walk(_x->right);
    }
}

template <class T>
void BinaryTree<T>::inorder_walk() const
{
    inorder_walk(root);
    std::cout << std::endl;
}

template<class T>
BinaryTreeNode<T>* BinaryTree<T>::min(Node* _x) const
{
    while(_x->left != NULL)
    {
        _x = _x->left;
    }
    return _x;
}

template<class T>
BinaryTreeNode<T>* BinaryTree<T>::max(Node* _x) const
{
    while(_x->right != NULL)
    {
        _x = _x->right;
    }
    return _x;
}

template<class T>
BinaryTreeNode<T>* BinaryTree<T>::predecessor(Node* _x) const
{
    Node* x = _x;
    if (x->left != NULL)
    return max(x->left);
    Node* y = x->parent;
    while (y != NULL && x == y->left)
    {
    x = y;
        y = y->parent;
    }
    return y;
}

template<class T>
BinaryTreeNode<T>* BinaryTree<T>::successor(Node* _x) const
{
    Node* x = _x;
    if (x->right != NULL)
	return min(x->right);
    Node* y = x->parent;
    while (y != NULL && x == y->right)
    {
	    x = y;
	    y = y->parent;
    }
    return y;
}

template<class T>
BinaryTreeNode<T>* BinaryTree<T>::tree_search(T k) const
{
    Node* x  = root;
    while(x != NULL && k != x->data)
    {
        if(k < x->data)
        x = x->left;
        else x = x->right;
    }
    return x;
}

template <class T>
void BinaryTree<T>::insert(T _data)
{
    Node* y = NULL;
    Node* x = root;
    Node* p = new Node(_data);
    while (x != NULL)
    {
	y = x;
	if (p->data  < x->data)
	    x = x->left;
	else
	    x = x->right;
    }
    p->parent = y;
    if (y == NULL)
	root = p;
    else if (p->data < y->data)
	y->left = p;
    else
	y->right = p;
}

template<class T>
void BinaryTree<T>::insert(Node* _new)
{
    Node *y = NULL;
    Node *x = root;
    // Make sure that _new is a single node binary tree.
    _new->left = _new->right = NULL;
    while (x != NULL)
    {
	y = x;
	// The nodes less than to the left, then these greater than or
	// equal to to the right.
	if (_new->data < x->data)
	    x = x->left;
	else
	    x = x->right;
    }
    _new->parent = y;
    if (y == NULL)
	root = _new;
    // Here the decision rule has to same as above.
    else if (_new->data < y->data)
	y->left = _new;
    else
	y->right = _new;
    
}

template <class T>
void BinaryTree<T>::transplant(Node* _u, Node* _v)
{
    if (_u == NULL)
    {
	std::cerr << "Error! Can not transplant to a NULL."<< std::endl;
	std::exit(-1);
    }
    if (_u->parent == NULL)
	root = _v;   
    else if (_u == _u->parent->left)
	_u->parent->left = _v;
    else
	_u->parent->right = _v;
//    if (_v != nil)
    _v->parent = _u->parent;
    
}

template <class T>
void BinaryTree<T>::del(Node* _x)
{
    if (_x->left == NULL)
	transplant(_x, _x->right);
    else if (_x->right == NULL)
	transplant(_x, _x->left);
    else
    {
	Node *y = min(_x->right);
	// If y is not a child of _x, which means y is _x's grand
	// child or lower.
	if (y->parent != _x)   
	{
	    // This actually make a circle. Dangrous! Here we
	    // transplant right child of y to y, but we didn't lose
	    // y. we just make the right child of y become y's
	    // parent's child.
	    transplant(y, y->right);
	    // Then make the right child of _x become y's right
	    // child. And still we didn't lose the original right
	    // child of y, it is still y's parent's child.
	    y->right = _x->right;
	    y->right->parent = y;
	    // Suppose z is y's parent in the beginning, till now, y's
	    // right child become z's child, and it's original place
	    // has taken by _x's right child. test.

	}
	// If y is _x's child, then y is _x's right child because it's
	// a successor of _x. And if not, _x's right child has already
	// transplant to y's right child, while the original right
	// child of y has already transplant to y's parent's
	// child(still in the right subtree of the original _x, now is
	// inside the right subtree of y). In the next we replace _x
	// with y(with the original right subtree of y together with
	// the right subtree of _x), and put the left child of _x to
	// the left child place of y(it's empty before). ineresting!
	transplant(_x, y);
	y->left = _x->left;
	y->left->parent = y;
	// Till now every thing is at the right place excepts _x.
    }
    delete _x;
    
}